/* hashmap implemented functions . 
 * @author chenxin <chenxin619315@gmail.com>
 * 结构类似于动态数组+链表, 通过key算出hash值
 * 根据hash值算出数组下标
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "mathlib.h"
#include "hashmaplib.h"

#ifdef DEBUG
	#define debug_print printf
#else
	#define debug_print
#endif

static int cel_hashmap_init(cel_hashmap_t *map, int opacity, float factor);
static cel_hashmap_node_t **create_node_blocks(unsigned int _blocks);
static int cel_hashmap_destroy(cel_hashmap_t *hash, cel_hashmap_rcb_fn_t relfunc);
#define cel_hash(str)	cel_bkdr_hash(str)
static cel_hashmap_node_t *create_hashmap_node(char *key,void *value, cel_hashmap_node_t *next);
static void rebulid_hash(cel_hashmap_t *hash);

/* create a cel hashmap with a specified length and factory */
cel_hashmap_t *new_cel_hash_map_opacity(int opacity, float factor)
{
	cel_hashmap_t *map = (cel_hashmap_t *)malloc(sizeof(cel_hashmap_t));
	if(map == NULL) {
		perror("new_cel_hash_map_opacity malloc");
	}

	if(cel_hashmap_init(map, opacity, factor) < 0)
	{
		free(map);
	}

	return map;
}

/* initialize the specified hashmap */
static int cel_hashmap_init(cel_hashmap_t *map, int opacity, float factor)
{
	map->table = create_node_blocks(opacity);
	if(map->table == NULL)
		return -1;
	
	map->length = opacity;
	map->size = 0;
	map->factor = factor;
	map->threshold = (unsigned int)(factor * opacity);

	return 0;
}

/* create a new hashmap node */
static cel_hashmap_node_t **create_node_blocks(unsigned int _blocks)
{
	register unsigned i;
	cel_hashmap_node_t **table = NULL;

	table = (cel_hashmap_node_t **)calloc(_blocks, sizeof(cel_hashmap_node_t *));
	if(table == NULL) {
		perror("create_node_block malloc");
		return NULL;
	}

	for(i = 0; i < _blocks; i++)
	{
		table[i] = NULL;
	}
	return table;
}

/* free the specified cel hashmap. callback function will be invoked for 
 * each node, if it is not null
 */
void free_cel_hashmap(cel_hashmap_t **hash, cel_hashmap_rcb_fn_t relfunc)
{
	if(hash == NULL)
		return;

	if(*hash != NULL)
	{
		cel_hashmap_destroy(*hash, relfunc);
		free(*hash);
		*hash = NULL;
	}
}

static int cel_hashmap_destroy(cel_hashmap_t *hash, cel_hashmap_rcb_fn_t relfunc)
{
	register unsigned idx;

	cel_hashmap_node_t *e, *next;

	if(hash != NULL)
	{
		for(idx = 0; idx < hash->length; idx++)
		{
			for(e = hash->table[idx]; e != NULL;)
			{
				next = e->next;
				if(relfunc != NULL) {
					relfunct(e);
				}
				free(e);
				e = next;
			}
		}
		/* free the table bucket */
		free(hash->table);
		hash->table = NULL;
	}

	return 0;
}

/* associated the key with the specified value */
void *cel_hashmap_put(cel_hashmap_t *hash, char *key, void *value)
{
	void *v;
	cel_hashmap_node_t *e;
	unsigned int hcode = cel_hash(key);
	unsigned int idx = hcode % hash->length;

	for(e = *(hash->table + idx); e != NULL; e = e->next)
	{
		if(key == e->key || strcmp(key, e->key) == 0)
		{
			v = e->value.ptr;
			e->value.ptr = value;
			return v;
		}
	}

	hash->table[idx] = create_hashmap_node(key, value, hash->table[idx]);

	e = hash->table[idx];
	e->hash = hcode;

	hash->size++;
	if(hash->size > hash->threshold)
	{
		rebuild_hash(hash);
	}

	return NULL;
}

static cel_hashmap_node_t *create_hashmap_node(char *key, void *value, cel_hashmap_node_t *next)
{
	cel_hashmap_node_t *node = (cel_hashmap_node_t *)malloc(sizeof(cel_hashmap_node_t));
	if(node == NULL) {
		perror("create_hashmap_node node");
	}

	node->key = key;
	node->value.ptr = value;
	node->next = next;

	return node;
}

/* hash rebuild mapping。扩展hashmap表的大小 */
static void rebulid_hash(cel_hashmap_t *hash)
{
	register unsigned int i;
	unsigned int idx;

	unsigned int length = cel_next_prime(hash->length *2 + 1);
	cel_hashmap_node_t **_table = create_node_blocks(length);
	cel_hashmap_node_t *e, *next;

	if(_table == NULL) {
		return;
	}

	for(i = 0; i < hash->length; i++)
	{
		e = *(hash->table + i);
		if(e != NULL)
		{
			do {
				next = e->next;
				idx = e->hash % length;
				e->next = _table[idx];
				_table[idx] = e;
				e = next;
			}while(e != NULL);
		}
	}

	/* free the old bucket */
	free(hash->table);
	hash->table = _table;
	hash->length = length;
	hash->threshold = (unsigned int)(hash->factor * length);
}

/* remove the mapping associated with the specified key */
void *cel_hashmap_remove(cel_hashmap_t *hash, char *key, cel_hashmap_rcb_fn_t rfunc)
{
	void *v;
	cel_hashmap_node_t *e, *prev = NULL;
	unsigned int idx = cel_hash(key) % hash->length;

	for(e = hash->table[idx]; e != NULL; prev = e, e = e->next)
	{
		if(key == e->key || strcmp(key, e->key) == 0)
		{
			if(prev == NULL)
			{
				hash->table[idx] = e->next;
			}
			else
			{
				prev->next = e->next;
			}
			v = e->value.ptr;

			if(rfunc != NULL) {
				rfunc(e);
			}
			/* free the removed node */
			free(e);
			hash->size--;
			return v;
		}
	}
	return NULL;
}

/* get the value associated with the specified key */
void *cel_hashmap_get(cel_hashmap_t *hash, char *key)
{
	cel_hashmap_node_t *e;
	unsigned int idx = cel_hash(key) % hash->length;

	for(e = hash->table[idx]; e != NULL; e = e->next)
	{
		if(key == e->key || strcmp(key, e->key) == 0)
		{
			return e->value.ptr;
		}
	}

	return NULL;
}

/* check the existence of the mapping associated with the specified key */
int cel_hashmap_exists(cel_hashmap_t *hash, char *key )
{
	cel_hashmap_node_t *e;
	unsigned int idx = cel_hash(key) % hash->length;

	for(e = hash->table[idx]; e != NULL; e = e->next) 
	{
		if(key == e->key || strcmp(key, e->key) == 0 ) 
		{
			return 1;
		}
	}

	return 0;
}

/* replace the value associated with the specified key. */
void *cel_hashmap_set(cel_hashmap_t *hash, char *key, void *value)
{
	void * v;
	cel_hashmap_node_t *e;
	unsigned int idx = cel_hash(key) % hash->length;

	for(e = hash->table[idx]; e != NULL; e = e->next) 
	{
		if( key == e->key || strcmp( key, e->key ) == 0) 
		{
			v = e->value.ptr;
			e->value.ptr = value;
			return v;
		}
	}

	return NULL;
}




